\documentclass[main]{subfiles} 

\begin{document}
	\section{SPFA复习【20250206】}
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P3385}{洛谷-P3385}}
	\href{https://oi-wiki.org/graph/shortest-path/\#\%E9\%98\%9F\%E5\%88\%97\%E4\%BC\%98\%E5\%8C\%96spfa}{SPFA判负环}模板题，会卡SLF优化，加上D´Esopo–Pape才能过。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P5960}{洛谷-P5960}}
	\href{https://oi-wiki.org/graph/diff-constraints/}{SPFA差分约束}模板题。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P2136}{洛谷-P2136}}
	\href{https://oi-wiki.org/graph/shortest-path/\#\%E9\%98\%9F\%E5\%88\%97\%E4\%BC\%98\%E5\%8C\%96spfa}{SPFA判负环}模板题，注意题目中并没有说$1$和$N$谁是起点，所以要做两遍SPFA。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1993}{洛谷-P1993}}
	对于$\geq$的不等式两边同时乘以$-1$，即可转为\href{https://oi-wiki.org/graph/diff-constraints/}{SPFA差分约束}模板题。
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc061\_d\#author=DeepSeek\_zh}{AtCoder-abc061\_d}}
	最长路问题。要注意题目只有在从$1$到$N$的路径上存在的正环才输出inf，需要先DFS出$N$能到的点集$V^{'}$，在$V^{'}$的诱导子图上用SPFA求$1$到$N$的最长路。

	\subsection{\href{https://vjudge.net/problem/AtCoder-abc137\_e\#author=DeepSeek\_zh}{AtCoder-abc137\_e}}
	将每条边的边权减$P$，问题转化为最长路问题。要注意题目只有在从$1$到$N$的路径上存在的正环才输出-1，需要先DFS出$N$能到的点集$V^{'}$，在$V^{'}$的诱导子图上用SPFA求$1$到$N$的最长路，最后的答案要和0取max。
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc237\_e\#author=DeepSeek\_zh}{AtCoder-abc237\_e}}
	混在SPFA题单里的Dijkstra题目。
	
	将所有的边权乘以-1，问题转化为最短路问题。观察到这题边权的特殊性，根据\href{https://oi-wiki.org/graph/shortest-path/\#johnson-\%E5\%85\%A8\%E6\%BA\%90\%E6\%9C\%80\%E7\%9F\%AD\%E8\%B7\%AF\%E5\%BE\%84\%E7\%AE\%97\%E6\%B3\%95}{Johnson算法}的思想，海拔$h$就是天然的势能函数，改造完成后，所有的边权非负可以跑Dijkstra，最后的答案为$max\{h_1-h_i-dist_i\ |\ i\in[1,n]\}$
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P5905}{洛谷-P5905}}
	\href{https://oi-wiki.org/graph/shortest-path/\#johnson-\%E5\%85\%A8\%E6\%BA\%90\%E6\%9C\%80\%E7\%9F\%AD\%E8\%B7\%AF\%E5\%BE\%84\%E7\%AE\%97\%E6\%B3\%95}{Johnson算法}模板题，这题的数据卡了SLF+D´Esopo–Pape优化，不加任何优化的SPFA就能过。
	
	\subsection{Summary}
	\begin{itemize}
		\item 这么多年过去，SPFA已成明日黄花，对于各种优化都有卡掉的数据，所以对于SPFA应该把它当成是常数较小的Bellman-Ford，各种奇技淫巧的优化完全没有必要加了。
		\item 另外SPFA判断负环的根本逻辑是最短路边数不能超过$n-1$，能够通过入队次数来判断是因为不加优化的SPFA本质上是个按照边数顺序来扩展的BFS，每个点入队一次则最短路边数至少在原有的基础上加1。一旦加了其他优化SPFA就不是一个BFS了，所以就只能通过记录最短路边数而不是入队次数来判负环了。
	\end{itemize}

\end{document}